package com.arithmetic.sort;


/**
 * 排序
 *
 * 冒泡排序
 * 插入排序
 * 选择排序
 * 归并排序
 * 快速排序
 * 桶排序
 */
public class SortDemo {



    /**
     * 冒泡排序
     */
    // 冒泡排序，a表示数组，n表示数组大小
    public void bubbleSort(int[] a, int n) {
        if (n <= 1) return;
        for (int i = 0; i < n; ++i) {
            // 提前退出冒泡循环的标志位
            boolean flag = false;
            for (int j = 0; j < n - i - 1; ++j) {
                if (a[j] > a[j+1]) { // 交换
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                    flag = true;  // 表示有数据交换
                }
            }
            if (!flag) break;  // 没有数据交换，提前退出
        }
    }

    /**
     * 插入排序
     */
// 插入排序，a表示数组，n表示数组大小
    public void insertionSort(int[] a, int n) {
        if (n <= 1) return;

        for (int i = 1; i < n; ++i) {
            int value = a[i];
            int j = i - 1;
            // 查找插入的位置
            for (; j >= 0; --j) {
                if (a[j] > value) {
                    a[j+1] = a[j];  // 数据移动
                } else {
                    break;
                }
            }
            a[j+1] = value; // 插入数据
        }
    }

    /**
     * 选择排序
     */


    /**
     * 归并排序
     * // 归并排序算法, A是数组，n表示数组大小
     *     merge_sort(A, n) {
     *         merge_sort_c(A, 0, n-1)
     *     }
     *
     *     // 递归调用函数
     *     merge_sort_c(A, p, r) {
     *         // 递归终止条件
     *         if p >= r  then return
     *
     *                 // 取p到r之间的中间位置q
     *                 q = (p+r) / 2
     *         // 分治递归
     *         merge_sort_c(A, p, q)
     *         merge_sort_c(A, q+1, r)
     *         // 将A[p...q]和A[q+1...r]合并为A[p...r]
     *         merge(A[p...r], A[p...q], A[q+1...r])
     *     }
     */
    public void demo3(){

    }


}
